package practise.alogrithm.hundredInterviewQuestions.secondTime;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by Richard on 7/26/2014.
 */
public class VerifyArrayFromATree {
    public boolean verify(List<Integer> array){
        if(array.size()<=2){
            return true;
        }

        int indexForDivide = -1;
        int cmp = array.get(array.size()-1);
        for(int index = 0; index<array.size()-1;index++){
            if(array.get(index)>cmp){
                if(indexForDivide<0)// only allow change the index once
                    indexForDivide=index;
            }
            if(array.get(index)<=cmp && indexForDivide>=0){
                return false;
            }
        }

        return verify(new ArrayList<>(array.subList(0,indexForDivide-1)))&verify(new ArrayList<>(array.subList(indexForDivide,array.size()-2)));
    }

    public static void main(String[] args){
        VerifyArrayFromATree verifyArrayFromATree = new VerifyArrayFromATree();
        System.out.println("Result:"+verifyArrayFromATree.verify(new ArrayList<>(Arrays.asList(new Integer[]{5,7,6,9,11,10,8}))));
    }
}
